%% This is file `elsarticle-template-5-harv.tex',
%%
%% Copyright 2009 Elsevier Ltd
%%
%% This file is part of the 'Elsarticle Bundle'.
%% ---------------------------------------------
%%
%% It may be distributed under the conditions of the LaTeX Project Public
%% License, either version 1.2 of this license or (at your option) any
%% later version.  The latest version of this license is in
%%    http://www.latex-project.org/lppl.txt
%% and version 1.2 or later is part of all distributions of LaTeX
%% version 1999/12/01 or later.
%%
%% The list of all files belonging to the 'Elsarticle Bundle' is
%% given in the file `manifest.txt'.
%%
%% Template article for Elsevier's document class `elsarticle'
%% with harvard style bibliographic references
%%
%% $Id: elsarticle-template-5-harv.tex 159 2009-10-08 06:08:33Z rishi $
%% $URL: http://lenova.river-valley.com/svn/elsbst/trunk/elsarticle-template-5-harv.tex $
%%
\documentclass[preprint,authoryear,12pt]{elsarticle}

%% Use the option review to obtain double line spacing
%% \documentclass[authoryear,preprint,review,12pt]{elsarticle}

%% Use the options 1p,twocolumn; 3p; 3p,twocolumn; 5p; or 5p,twocolumn
%% for a journal layout:
%% \documentclass[final,authoryear,1p,times]{elsarticle}
%% \documentclass[final,authoryear,1p,times,twocolumn]{elsarticle}
%% \documentclass[final,authoryear,3p,times]{elsarticle}
%% \documentclass[final,authoryear,3p,times,twocolumn]{elsarticle}
%% \documentclass[final,authoryear,5p,times]{elsarticle}
%% \documentclass[final,authoryear,5p,times,twocolumn]{elsarticle}

%% if you use PostScript figures in your article
%% use the graphics package for simple commands
%% \usepackage{graphics}
%% or use the graphicx package for more complicated commands

\usepackage{listings}
\lstset{language=SQL,morekeywords={PREFIX,java,rdf,rdfs,url}}
\usepackage{graphicx}
%% or use the epsfig package if you prefer to use the old commands
\usepackage{epsfig}

%% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
%% The amsthm package provides extended theorem environments
%% \usepackage{amsthm}

%% The lineno packages adds line numbers. Start line numbering with
%% \begin{linenumbers}, end it with \end{linenumbers}. Or switch it on
%% for the whole article with \linenumbers after \end{frontmatter}.
%% \usepackage{lineno}

%% natbib.sty is loaded by default. However, natbib options can be
%% provided with \biboptions{...} command. Following options are
%% valid:

%%   round  -  round parentheses are used (default)
%%   square -  square brackets are used   [option]
%%   curly  -  curly braces are used      {option}
%%   angle  -  angle brackets are used    <option>
%%   semicolon  -  multiple citations separated by semi-colon (default)
%%   colon  - same as semicolon, an earlier confusion
%%   comma  -  separated by comma
%%   authoryear - selects author-year citations (default)
%%   numbers-  selects numerical citations
%%   super  -  numerical citations as superscripts
%%   sort   -  sorts multiple citations according to order in ref. list
%%   sort&compress   -  like sort, but also compresses numerical citations
%%   compress - compresses without sorting
%%   longnamesfirst  -  makes first citation full author list
%%
%% \biboptions{longnamesfirst,comma}

% \biboptions{}

\usepackage{hyperref}
\journal{Expert Systems with Applications}

\begin{document}

\begin{frontmatter}

%% Title, authors and addresses

%% use the tnoteref command within \title for footnotes;
%% use the tnotetext command for the associated footnote;
%% use the fnref command within \author or \address for footnotes;
%% use the fntext command for the associated footnote;
%% use the corref command within \author for corresponding author footnotes;
%% use the cortext command for the associated footnote;
%% use the ead command for the email address,
%% and the form \ead[url] for the home page:
%%
%% \title{Title\tnoteref{label1}}
%% \tnotetext[label1]{}
%% \author{Name\corref{cor1}\fnref{label2}}
%% \ead{email address}
%% \ead[url]{home page}
%% \fntext[label2]{}
%% \cortext[cor1]{}
%% \address{Address\fnref{label3}}
%% \fntext[label3]{}

%\title{vRank: a Vocabulary for Ranking Data}
\title{vRank: towards a formal model for sharing and reusing ranking}

%% use optional labels to link authors explicitly to addresses:
%% \author[label1,label2]{<author name>}
%% \address[label1]{<address>}
%% \address[label2]{<address>}

\author{Antonio J. Roa-Valverde}

\address{Semantic Technology Institute\\
University of Innsbruck\\
Technikerstrasse 21a, 6020\\
Innsbruck, Austria\\
antonio.roa@sti2.at
}

\begin{abstract}
%% Text of abstract
In this paper we present our efforts towards the design of vRank, the  ``Vocabulary for Ranking'', a vocabulary that allows to formally materialize ranking data algorithms. We justify the need for such a vocabulary and we show some potential applications in the context of Linked Data consumption. 
\end{abstract}

\begin{keyword}
%% keywords here, in the form: keyword \sep keyword
ranking \sep linked data \sep data consumption \sep ontology
%% MSC codes here, in the form: \MSC code \sep code
%% or \MSC[2008] code \sep code (2000 is the default)

\end{keyword}

\end{frontmatter}

% \linenumbers

%% main text
\section{Introduction}
\label{lbl:introduction}
[Gain of attention of linked data. From data publication to data consumption. Different consumption strategies in the scope of linked data]. 

A great part of the research in the field of semantic search focuses on proposing new ranking algorithms [cite examples], being most of them adaptations to the well-known PageRank algorithm \citep{Brin1998}. 

Till now, users of ranking algorithms (mostly through search engines) do not have the possibility of deciding how they want the data to be ranked for them. Most of the services offered by data providers are not flexible and impose their relevance models to data consumers. This design policy presents an important inconvenient regarding to data consumption: what is relevant for a user might not be relevant for another one and viceversa. In this way, there is a need for a mechanism that allows data consumers to decide how they want the data to be ranked, as they know better than anyone else what their preferences for consuming the requested data are. 

A possible way of implementing this mechanism is described through this paper. We propose vRank, the ``Vocabulary for Ranking", that addresses the modeling of ranking approaches to provide an efficient and flexible vehicle for data consumption. We focus on the scope of the Web of Data, however we remark that vRank practical applications are not restricted to the linked data domain.

Different methodologies for developing vocabularies have been suggested in the field of ontology engineering \citep{Uschold1995, Corcho2003}. In our attempt for developing vRank we have addressed the following tasks:

\begin{itemize}
\item Identification of needs for the proposed vocabulary.
\item Vocabulary design and implementation.
\item Evaluation.
\item Documentation.
\end{itemize}  

The rest of this paper is structured as follows...

\section{Background}
\label{lbl:background}
A ranking algorithm implements a function, which accepts a set of items and returns an ordered version of the set without modifying the items. The function is implemented taking into account certain preferences that determine the order of the items. In this way, the same collection of items could be ranked following different approaches, i.e. different order functions. 
Formally, a ranking algorithm implements a function of total order $f: X \rightarrow \Re$ such that for any $a, b \in X: f(a) \leq f(b) \leftrightarrow a \prec b$, where $\prec$ defines a binary relationship on the set $X$. Note that $\prec$ makes reference to the factor that guides the ranking strategy.

%\begin{figure}[htbp!]
%\begin{center}
%\epsfig{file=figures/algo-arch.png}
%\caption{{\bf Structure of a ranking algorithm}}
%\label{fig:fig1}
%\end{center}
%\end{figure}

Figure \ref{fig:fig1} depicts the components that integrate the functionality of a ranking algorithm. The input to any ranking method is a bunch of raw data that needs to be inspected to get the relevant information out of it. This task is carried out by the feature extractor, which generates a data model that will be used for the ranking function described above to produce the ranked set of items. The feature extractor together with the data structures that allocate the data model and the ranking function compose the functional architecture of the ranking algorithm.


\section{Purpose of vRank}
\label{lbl:purpose}
The purpose of vRank is to provide data consumers with a standardized, formal, unambiguous, reusable and extendable way of representing ranking computations. The way data is consumed depends strongly on what is relevant for data consumers. When data providers offer some kind of ranking service, obviously they cannot contemplate all possible relevance models of consumers. Therefore the need for the functionality that vRank tries to implement. 

The following requirements have guided the design of vRank:

\begin{enumerate}
\item We need to unify the way ranking algorithms are developed in order to promote reusability and evaluation
\item  We need a common and accepted model to homogenize the exploitation of ranking services.
\item  We need to separate data from any kind of assumption regarding to publication and consumption (data providers and consumers may not share the same interests).
\end{enumerate}

Offering ranking computations as part of the data can facilitate its consumption in several ways:

\begin{itemize}
\item Different relevance models from diverse ranking strategies can coexist within the same dataset. Consumers can adapt data requests to their relevance expectations.
\item Data ranking becomes open and shareable. Consumers can reuse a specific way of ranking a dataset. If existent ranking approaches do not suit consumers' needs, they can extend the dataset with their own model.
\item Consumers can reuse ranking scores in order to evaluate and compare different strategies over a given dataset.
\item Consumers (and not data providers) can have control about how they want to consume data, giving more preference to what is more relevant. 
\end{itemize}



\subsection{Ranking crystallization}
Ranking algorithms rely on data structures that are used to compute the final scores of data items. Traditionally, these data structures are kept internally and inaccessible for data consumers. What data consumers get once the ranking process has finished is the ordering of the different items. This kind of behavior defines ranking algorithms as a black box, which makes very difficult, if not impossible, to reuse and share computations over existent data. 

We need to materialize the relevance models computed by ranking algorithms in a way that can be offered publicly and and can be queried by data consumers. The publication can be done ``easily" in RDF if we are able to come up with a vocabulary that models the ranking domain. This is actually what vRank has been defined for. 

%The approach to model this vocabulary could be similar to the VOID vocabulary [2]. If this vocabulary gets acceptation among developers of ranking algorithms, users could benefit of having different ranking scores for the same dataset, which would allow them to select the order in which they want the data. This selection could be done in a trivial way through SPARQL.
%On the other hand query languages like SPARQL do not support ranking in a native way. At most there are functions for sorting out the data (ORDER BY), which is basically inherited from the SQL language.

Regarding to the query, SPARQL\footnote{http://www.w3.org/TR/rdf-sparql-query/} is considered as the standard language for querying the Web of Data, however it does not support any kind of ranking apart from ORDER BY clauses. By adopting vRank it is not necessary to extend SPARQL with ranking support as the ranking can be made explicit within the dataset. Consumers do not need to learn a different query language or any kind of extension. They still can use ORDER BY clauses and just adapt their queries to use the adequate vRank triples (see section \ref{lbl:example}).

\subsection{Ranking evaluation}
The development of ranking algorithms maintain certain grade of parallelism with the evolution of the Semantic Web. While the first ranking algorithms were designed with the aim of ranking ontology documents \citep{Ding2004}, in a similar way to how traditional approaches rank HTML documents, the arrival of the Web of Data has changed the focus of ranking strategies towards information modeled as entities and their relationships \citep{Delbru2010}. In just a period of ten years the research on Semantic Web topics has delivered diverse kinds of works addressing the topic of ranking information following different approaches. 

Due to the different policies used in ranking is very difficult to establish a technical comparison to analyze the accuracy and precision of each algorithm in reference to others. The main explanation for this is that while there are different benchmarks and data sets to measure and compare the ranking strategies in the area of information retrieval \citep{Artiles2008, Kamps2008, Soboroff2006}, the same is still missing when referring to ranking on the Web of Data. Authors in \citep{Pound2010} justify the need for a benchmark applied to search and ranking on the Web of Data and establish the first steps towards a methodology for resource retrieval evaluation. 

One of the main contributions of vRank is that it helps to homogenize the way ranking services are exploited, so that third parties can compare and evaluate them. 

\subsection{Evolution of data}
In an open environment like the Web, data is always going under modifications and revisions. When data is updated, so must be the ranking scores associated to data items. A consumer may be interested about analyzing the ranking scores over the time in order to predict future changes that might affect her consumption patterns.

\subsection{Multirelevancy}
Consumers can make use of the available ranking scores to combine and compose their own ranking functions. The new obtained scores can be materialized and shared by using vRank.

\section{Vocabulary description}
\label{lbl:vocabulary}


\section{Example}
\label{lbl:example}

\section{Applications}

\section{Related work}
At the time of writing and to the best of our knowledge there are no similar approaches that try to solve the problem of ranking in the same way than vRank. The closest effort to vRank we have found has been developed by Ontotext\footnote{http://www.ontotext.com/} within the OWLIM RDF store\footnote{http://owlim.ontotext.com/display/OWLIMv50/OWLIM+Primer}. OWLIM implements an internal ranking mechanism named RDF Rank\footnote{http://owlim.ontotext.com/display/OWLIMv50/OWLIM-SE+RDF+Rank} that extends the behavior of PageRank. RDF Rank scores are made available via the predicate http://www.ontotext.com/owlim/RDFRank\#hasRDFRank, which is handled internally by OWLIM. The following excerpt shows an example of query making use of the ranking scores.

\begin{verbatim}
PREFIX rank: <http://www.ontotext.com/owlim/RDFRank#>
PREFIX opencyc-en: <http://sw.opencyc.org/2008/06/10/concept/en/>
SELECT * WHERE {
  ?Person a opencyc-en:Entertainer .
  ?Person rank:hasRDFRank ?rank .
}
ORDER BY DESC(?rank) LIMIT 100
\end{verbatim}

This mechanism is very similar to the way vRank scores are exploited. The biggest difference remains in the purpose of the model, i.e., in OWLIM the previous predicate has designed to be manipulated only internally and not to be shared publicly. Despite OWLIM offers the possibility of exporting RDF Rank values to an external file, their main purpose is to be used as initial activation values for the algorithm. In addition OWLIM does not contemplate the use of diverse ranking algorithms and therefore there is no implementation of this feature in the internal vocabulary.

\section{Conclusions and future work}
Evaluation in a concrete domain like life sciences

incremental ranking

brankia: provides a common framework for the development and testing of data ranking algorithms. Independent library that can be integrated within search engines or RDF data stores


\section{Use Case: Entity Summarization}
Since recent times, another topic related to ranking became more and more popular. In addition to the ranking of entities for search indexing, the ranking of an entity's property-value pairs has gained particular attention. This concept is most popularly manifested in the summaries of Google's Knowledge Graph (GKG). However, various different approaches have emerged this field \cite{relin,thalhammer,waitelonis,googleblog} and therefore, summarized versions Linked Open Data (LOD) can be published as Linked Data. The gain includes an increased ability to compare and select different Linked Data summarization approaches. It has to be noted that summaries commonly include rankings but also provide a cut-off or a selection mechanism. However, the latter step will play a minor role in the following as it succeeds the steps of ranking and its representation which state the the main focus of this contribution.\\

In the further reading of this section, GKG summaries will serve as a walk-through example in order to demonstrate the versatility of vRank and its applicability in various settings. In addition, we provide a data set which includes the GKG summaries of 60 movies randomly selected from the IMDb Top 250 list. The key challenges in appropriately modeling the scenario lie on two main issues:
\begin{enumerate}
\item Instead of entities, property-value pairs are ranked.
\item The rankings of property-value pairs are specific for one particular subject.
\end{enumerate}

The usage of property-value pairs in the context of ranking is first introduced in \cite{relin} where the authors use such combinations to define the concept of a feature. It is important to note that Entity Summarization is neither property nor object ranking but a ranking of the pairs composed out of properties and their according values (objects). Moreover, these rankings are only valid for a single entity as the importance of the same property-value pair (e.g. \texttt{production\_company, walt\_disney}) is usually perceived differently from entity to entity.



\renewcommand{\thelstlisting}{\arabic{lstlisting}} %% <- some hack
\begin{table}[ht]
\begin{lstlisting}[captionpos=t, caption={Reification for the ranking of property-value pairs.}, label=lst:propchain,
   basicstyle=\ttfamily,numbers=left,numberstyle=\tiny,frame=single]

<rdf:Statement rdf:about="http://movie.rank/234234">
<rdf:subject rdf:about=fb:en.pulp_fuction/>
<rdf:predicate rdf:about=fb:directed_by/>
<rdf:object rdf:about=fb:en.quentin_tarantino/>
</rdf:Statement>


<http://movie.rank/234234> vRank:hasRank ...
\end{lstlisting}
\vspace{-0.5cm}
\end{table}
%% The Appendices part is started with the command \appendix;
%% appendix sections are then done as normal sections
%% \appendix

%% \section{}
%% \label{}

%% References
%%
%% Following citation commands can be used in the body text:
%%
%%  \citet{key}  ==>>  Jones et al. (1990)
%%  \citep{key}  ==>>  (Jones et al., 1990)
%%
%% Multiple citations as normal:
%% \citep{key1,key2}         ==>> (Jones et al., 1990; Smith, 1989)
%%                            or  (Jones et al., 1990, 1991)
%%                            or  (Jones et al., 1990a,b)
%% \cite{key} is the equivalent of \citet{key} in author-year mode
%%
%% Full author lists may be forced with \citet* or \citep*, e.g.
%%   \citep*{key}            ==>> (Jones, Baker, and Williams, 1990)
%%
%% Optional notes as:
%%   \citep[chap. 2]{key}    ==>> (Jones et al., 1990, chap. 2)
%%   \citep[e.g.,][]{key}    ==>> (e.g., Jones et al., 1990)
%%   \citep[see][pg. 34]{key}==>> (see Jones et al., 1990, pg. 34)
%%  (Note: in standard LaTeX, only one note is allowed, after the ref.
%%   Here, one note is like the standard, two make pre- and post-notes.)
%%
%%   \citealt{key}          ==>> Jones et al. 1990
%%   \citealt*{key}         ==>> Jones, Baker, and Williams 1990
%%   \citealp{key}          ==>> Jones et al., 1990
%%   \citealp*{key}         ==>> Jones, Baker, and Williams, 1990
%%
%% Additional citation possibilities
%%   \citeauthor{key}       ==>> Jones et al.
%%   \citeauthor*{key}      ==>> Jones, Baker, and Williams
%%   \citeyear{key}         ==>> 1990
%%   \citeyearpar{key}      ==>> (1990)
%%   \citetext{priv. comm.} ==>> (priv. comm.)
%%   \citenum{key}          ==>> 11 [non-superscripted]
%% Note: full author lists depends on whether the bib style supports them;
%%       if not, the abbreviated list is printed even when full requested.
%%
%% For names like della Robbia at the start of a sentence, use
%%   \Citet{dRob98}         ==>> Della Robbia (1998)
%%   \Citep{dRob98}         ==>> (Della Robbia, 1998)
%%   \Citeauthor{dRob98}    ==>> Della Robbia


%% References with bibTeX database:

\bibliographystyle{model5-names}
\bibliography{vrank}

%% Authors are advised to submit their bibtex database files. They are
%% requested to list a bibtex style file in the manuscript if they do
%% not want to use model5-names.bst.

%% References without bibTeX database:

% \begin{thebibliography}{00}

%% \bibitem must have one of the following forms:
%%   \bibitem[Jones et al.(1990)]{key}...
%%   \bibitem[Jones et al.(1990)Jones, Baker, and Williams]{key}...
%%   \bibitem[Jones et al., 1990]{key}...
%%   \bibitem[\protect\citeauthoryear{Jones, Baker, and Williams}{Jones
%%       et al.}{1990}]{key}...
%%   \bibitem[\protect\citeauthoryear{Jones et al.}{1990}]{key}...
%%   \bibitem[\protect\astroncite{Jones et al.}{1990}]{key}...
%%   \bibitem[\protect\citename{Jones et al., }1990]{key}...
%%   \harvarditem[Jones et al.]{Jones, Baker, and Williams}{1990}{key}...
%%

% \bibitem[ ()]{}

% \end{thebibliography}

\end{document}

%%
%% End of file `elsarticle-template-5-harv.tex'.
